package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class offerII_0086 {
    public String[][] partition(String s) {
        List<List<String>> list=new ArrayList<>();
        List<String> path=new ArrayList<>();
        int num=s.length();
        boolean[][] dp=new boolean[num][num];
        for(int i=0;i<num;++i){
            dp[i][i]=true;
        }
        for(int i=0;i<num-1;++i){
            dp[i][i+1]=(s.charAt(i)==s.charAt(i+1));
        }
        for(int j=2;j<num;++j){
            for(int i=0;i+j<num;++i){
                dp[i][i+j]=(s.charAt(i)==s.charAt(i+j))&&dp[i+1][i+j-1];
            }
        }
        search(s,path,list,0,dp);
        int len=list.size();
        String[][] result=new String[len][];
        for(int i=0;i<len;++i){
            int tmplen=list.get(i).size();
            String[] tmp=new String[tmplen];
            for(int j=0;j<tmplen;++j){
                tmp[j]=list.get(i).get(j);
            }
            result[i]=tmp;
        }
        return result;
    }
    public void search(String s,List<String> path,List<List<String>> list,int index,boolean[][] dp){
        if(index>=s.length()){
            list.add(new LinkedList<>(path));
            return;
        }
        for(int i=index;i<s.length();++i){
            if(dp[index][i]){
                path.add(s.substring(index,i+1));
                search(s, path, list, i+1,dp);
                path.remove(path.size()-1);
            }
        }
    }
}
